package com.hot100.mid;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description:    二叉树的层序遍历
 * @date 2022/8/21 15:32
 */
public class Demo27 {

    /**
     * Definition for a binary tree node.
     * **/
      public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
         if(root==null){
             return res;
         }
         trackBack(root,0);

         return res;
    }

    private void trackBack(TreeNode root, int index) {
        if(root!=null){
            List<Integer> list;
            if(res.size()<index+1){
               list=new ArrayList<>();
               res.add(list);
            }else {
                list = res.get(index);
            }
           list.add(root.val);
           trackBack(root.left,index+1);
           trackBack(root.right,index+1);
        }
    }

}
